class Solution(object):
    def areSentencesSimilarTwo(self, sentence1, sentence2, similarPairs):
        """
        :type sentence1: List[str]
        :type sentence2: List[str]
        :type similarPairs: List[List[str]]
        :rtype: bool
        """
        d = {}
        if len(sentence1) != len(sentence2):
            return False
        n = len(sentence1)

        def find(x):
            if x not in d:
                d[x] = x
                return x
            else:
                if d[x] == x:
                    return x
                else:
                    d[x] = find(d[x])
                    return d[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                if rootx < rooty:
                    d[rooty] = rootx
                else:
                    d[rootx] = rooty

        for pair in similarPairs:
            union(pair[0], pair[1])
        for i in range(n):
            if sentence1[i] != sentence2[i]:
                if sentence1[i] not in d or sentence2[i] not in d:
                    return False
                else:
                    x1 = find(sentence1[i])
                    x2 = find(sentence2[i])
                    if x1 != x2:
                        return False
        return True


data = Solution()
sentence1 = ["great", "acting", "skills"]
sentence2 = ["fine", "drama", "talent"]
similarPairs = [["great", "good"], ["fine", "good"], ["drama", "acting"], ["skills", "talent"]]
print(data.areSentencesSimilarTwo(sentence1, sentence2, similarPairs))
